#include <iostream>
#include <sstream>
using namespace std;

#include "LinkedList.h"
#include "Stack.h"
#include "Heap.h"
#include "Queue.h"
#include "BinarySearch.h"
#include "MergeSort.h"
#include "MyString.h"
#include "RecoveryTree.h"
#include "LongestCommonString.h"

void LinkedListExample()
{
	LinkedList* list = new LinkedList();
	list->InitList();
	cout<<"Insert 1 2 3 4"<<endl;
	list->InsertListFirst(new LinkedListNode(4));
	list->InsertListFirst(new LinkedListNode(3));
	list->InsertListFirst(new LinkedListNode(2));
	list->InsertListFirst(new LinkedListNode(1));
	list->TranverseList();

	cout<<"Delete first 1 -- 2 3 4"<<endl;
	list->DeleteListFirst();
	list->TranverseList();

	cout<<"Delete last 4 -- 2 3"<<endl;
	list->DeleteListLast();
	list->TranverseList();

	cout<<"Insert last 6 -- 2 3 6"<<endl;
	list->InsertListLast(new LinkedListNode(6));
	list->TranverseList();

	cout<<"Insert 5 at pos 3 -- 2 3 5 6"<<endl;
	list->InsertListPos(3, new LinkedListNode(5));
	list->TranverseList();

	cout<<"Delete 3 at pos 2 -- 2 5 6"<<endl;
	list->DeleteListPos(2);
	list->TranverseList();

	cout<<"Insert order 10 -- 2 5 6 10"<<endl;
	list->InsertOrderList(new LinkedListNode(10));
	list->TranverseList();

	cout<<"Delete value 10 -- 2 5 6"<<endl;
	list->DeleteListValue(new LinkedListNode(10));
	list->TranverseList();

	cout<<"Update value 100 at pos 1 -- 100 5 6"<<endl;
	list->UpdateDataInList(1, new LinkedListNode(100));
	list->TranverseList();

	cout<<"Update value 200 at pos 2 -- 100 200 6"<<endl;
	list->UpdateDataInList(2, new LinkedListNode(200));
	list->TranverseList();

	cout<<"Get value at pos 2 -- 200"<<endl;
	cout<<list->GetData(2)<<endl;

	cout<<"Clear list -- "<<endl;
	list->ClearList();
	list->TranverseList();

	cout<<"Is empty -- OK"<<endl;
	if(list->IsListEmpty())
		cout<<"OK"<<endl;

	delete list;
}

void StackExample()
{
	Stack * stack = new Stack();
	int i=0;
	cout<<"Push into stack --> ";
	for(i=0; i<10; i++)
	{
		stack->Push(i);
		cout<<i<<" ";
	}
	cout<<endl;

	cout<<"Pop from stack --> "<<endl;
	for(i=0; i<10; i++)
	{
		cout<<stack->Peek()<<" ";
		cout<<stack->Pop()<<endl;
	}
	cout<<endl;

	if(stack->IsEmpty())
		cout<<"OK"<<endl;

	delete stack;
}

void HeapExample()
{
	Heap * heap = new Heap();

	cout<<"Build a heap with 135246"<<endl;
	int array[] = {1, 3 ,5, 2, 4, 6};
	heap->Build(array, 6);

	cout<<"Show 1 2 3 4 5 6, sort array by heap"<<endl;
	for(int i=0; i<6; i++)
	{
		cout<<heap->Get()<<" ";
		heap->Delete();
	}
	cout<<endl;

	delete heap;
}

void QueueExample()
{
	Queue * queue = new Queue();

	for(int i=0; i<10; i++)
	{
		queue->EnQueue(i);
	}

	while(!queue->IsEmpty())
	{
		cout<<queue->FrontQueue()<<" ";
		cout<<queue->DeQueue()<<endl;
	}
}


string compressBad(string  str)  
{
	string  mystr  = "";
	char  last  =  str[0];
	int  count  = 1;
	stringstream ss;
	for (int  i = 1; i < str.length();  i++) 
	{
		if  (str[i]  == last)  
		{  //  Found  repeat  char
			count++;
		} 
		else 
		{ // Insert char count, and update last char
			
			ss<<last<<count;
			mystr += ss.str();
			last = str[i];
			count = 1;
		}
	}
	ss<<last<<count;
	return ss.str();
}

void BinarySearchExample()
{
	int array[] = {0,1,2,3,4,5,6,7,8,9};
	int key = 4;
	int length = sizeof(array);

	cout<<"recursive "<<BinarySerach_Recursive(array, 0, length-1, key)<<endl;
	cout<<"iterasive "<<BinarySerach_Iterative(array, 0, length-1, key)<<endl;

}

void RecoveryTreeExample()
{
	int pre[] = {1,2,4,12,5,13,3,6,7,9,10};
	int mid[] = {4,12,2,13,5,1,6,9,10,7,3};
	/*int pre[] = {-1,2,3};
	int mid[] = {3,2,-1};*/
	int index = -1;
	int length = sizeof(pre)/sizeof(int);
	TreeNode * root = RecoveryTree(pre, mid, 0 , length, index);
	assert(index == (length-1));
	PrintTreePreOrder(root);
	cout<<endl;
	PrintTreeMidOrder(root);
}

void main()
{
	//LinkedListExample();
	//StackExample();
	//HeapExample();
	//QueueExample();

	//BinarySearchExample();

	//cout<<compressBad("aabbcc")<<endl;

	/*char src[] = "Hello";
    cout<<"src: "
        <<src
        <<endl;
    
    char dst[1024];
    mystrcpy(dst, src);
    cout<<"dst: "
        <<dst
        <<endl;*/

/* Set up the list */

	//int list[LEN], i;
	//for (i = 0; i < LEN; i++) { list[i] = rand() % MAXEL; }
 //
	///* Do merge sort and print before/after */
	//printf("Before sort: ");
	//print_list(list, LEN);
 //
	//mergesort(list, LEN);
 //
	//printf("After sort: ");
	//print_list(list, LEN);


	//RecoveryTreeExample();


	cout<<Compare("abcdefg", "bcbcd");
}
